package org.example.leetcode;

import java.util.*;

/**
 * @version 1.0.0
 * @author: lynn
 * @description: 自习室占用的问题
 * @date: 2021/8/9 15:20
 */
public class LC57 {
    public static void main(String[] args) {
        LC57 lc=new LC57();
        /*int[][] intervals= {{1,2},{3,5},{6,7},{8,10},{12,16}};
        int[] newInterval={4,8};*/
        int[][] intervals={{1,3},{4,6}};
        int[] newInterval={6,8};
        int[][] res=lc.insert(intervals,newInterval);
        for (int i=0;i<res.length;i++){
            System.out.println(Arrays.toString(res[i]));
        }
    }

    // fixme https://www.bilibili.com/video/BV1Qa4y1h7Zp?from=search&seid=181822370504721555
    //巧妙的地方是更新newInterval，这个是核心，就是满足条件一直更新
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int i=0;
        List<int[]> list=new ArrayList<>();

        while (i<intervals.length && intervals[i][1]<newInterval[0]){
            list.add(intervals[i]);
            i++;
        }

        while (i<intervals.length && intervals[i][0]<=newInterval[1]){
            newInterval[0]=Math.min(intervals[i][0],newInterval[0]);
            newInterval[1]=Math.max(intervals[i][1],newInterval[1]);
            i++;
        }
        list.add(newInterval);
        //fixme 以上的步骤是 反推的，到这里之后 intervals[i][0] > newInterval[1] ,到这里的话，肯定是merge完了，新的开始
        while (i<intervals.length){
            list.add(intervals[i]);
            i++;
        }
        return list.toArray(new int[list.size()][2]);
    }
}
